package 最小生成树;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;

public class minimumSpanningTree {

    static final int N = 210, INF = 9999;
    static int n;//点的数量（城市的数量）
    static int m;//边的数量
    static int choose;//主函数用来选择模块的遍量
    static int ans;//保存最小生成树代价
    static int algorithmModel;//选择哪种算法进行计算
    static boolean isContinue = true;//是否结束程序运行
    static int[] dist;//存最小生成树的权值的数组
    static boolean[] st;//每个点是否被选过

    static int[][] ad, temp;//邻接矩阵和器副本

    static class Edge {
        int a, b, w;

        public Edge(int a, int b, int w) {
            this.a = a;
            this.b = b;
            this.w = w;
        }
    }

    static int[] p;
    static Edge[] edges;//存每条边的结构体数组

    static HashMap<Integer, String> map = new HashMap<>();
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int nextInt() throws Exception {
        in.nextToken();
        return (int) in.nval;
    }

    static String next() throws Exception {
        in.nextToken();
        return in.sval;
    }

    /**
     * @throws Exception
     */
    static void addCity() throws Exception {
        System.out.println("请输入要添加城市的数量");
        int cityNum = nextInt();
        while (cityNum-- > 0) {
            System.out.println("输入：城市编号 城市名");
            int number = nextInt();
            String cityName = next();
            if (map.containsKey(number)) {
                System.out.println("该城市已经存在，请添加其他城市");
            } else {
                map.put(number, cityName);
                n--;
            }
        }
    }

    static void chooseInput() throws Exception {
        System.out.println("请选择算法：");
        algorithmModel = nextInt();
        switch (algorithmModel) {
            default:
                System.out.println("输入错误");
                break;
            case 1:
                inputPrim();
                break;
            case 2:
                inputKruskal();
                break;

        }
    }

    static void inputPrim() throws Exception {
        System.out.println("输入格式：点 点 边");
        System.out.println("请输入点，边的数量(即 n m)");
        n = nextInt();
        m = nextInt();
        dist = new int[n + 1];
        ad = new int[n + 1][n + 1];
        st = new boolean[n + 1];
        temp = new int[n+1][n+1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) {
                    ad[i][j] = 0;
                    temp[i][j] = ad[i][j];

                } else {
                    ad[i][j] = INF;
                    temp[i][j] = ad[i][j];
                }
            }
        }

        while (m-- > 0) {
            int a = nextInt();
            int b = nextInt();
            int c = nextInt();
            if (!map.containsKey(a) && !map.containsKey(b)) {
                if (!map.containsKey(a)) {
                    System.out.println("不存在" + a + "号城市，请重新输入或添加该城市");
                } else if (!map.containsKey(b)) {
                    System.out.println("不存在" + b + "号城市，请重新输入或添加该城市");
                } else {
                    System.out.println("不存在" + a + "和" + b + "号城市，请重新输入或添加该城市");
                }

            }
            ad[a][b] = Math.min(ad[a][b], c);
            ad[b][a] = ad[a][b];
            temp[a][b] = ad[a][b];

        }
//        for (int[] x: ad){
//            System.out.println(Arrays.toString(x));
//        }
        ans = prim();
    }

    static void inputKruskal() throws Exception {
        System.out.println("输入格式：点 点 边");
        System.out.println("请输入点，边的数量(即 n m)");
        n = nextInt();
        m = nextInt();
        edges = new Edge[m];
        p = new int[m + 1];

        for (int i = 0; i < m; i++) {
            int a = nextInt();
            int b = nextInt();
            int c = nextInt();
            if (!map.containsKey(a) && !map.containsKey(b)) {
                if (!map.containsKey(a)) {
                    System.out.println("不存在" + a + "号城市，请重新输入或添加该城市");
                } else if (!map.containsKey(b)) {
                    System.out.println("不存在" + b + "号城市，请重新输入或添加该城市");
                } else {
                    System.out.println("不存在" + a + "和" + b + "号城市，请重新输入或添加该城市");
                }
                break;
            }

            edges[i] = new Edge(a, b, c);
        }
        ans = kruskal();
    }

    static void showPrimInput() {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i != j) {
                    if (temp[i][j] > INF * 2 / 3) {
                        System.out.println(map.get(i) + "到" + map.get(j) + "不能直接到达");
                    } else {
                        System.out.println(map.get(i) + "到" + map.get(j) + "的距离为" + temp[i][j] + "万公里");
                    }
                }
            }
        }

    }

    static void showKruskalInput() {
        for (int i = 0; i < m; i++) {
            if (edges[i].w > INF * 2 / 3) {
                System.out.println(map.get(edges[i].a) + "到" + map.get(edges[i].a) + "不能直接到达");
            } else {
                System.out.println(map.get(edges[i].a) + "到" + map.get(edges[i].b) + "的距离为" + edges[i].w + "万公里");
            }

        }

    }

    static void showInput() {
        switch (algorithmModel) {
            default:
                System.out.println("输入错误");
                break;
            case 1:
                showPrimInput();
                break;
            case 2:
                showKruskalInput();
                break;
        }
    }

    static void showCity() {
        for (Map.Entry<Integer, String> entry : map.entrySet()) {
            System.out.println(entry.getKey() + " " + entry.getValue());
        }
    }

    static void isConnected() {
        if (ans == INF) {
            System.out.println("此图不连通");
        }else {
            System.out.println("此图连通");
        }
    }

    static void showMinCost() {
        if (ans == INF) {
            System.out.println("此图不连通");
        }else {
            System.out.println("最小生成树的代价为"+ans);
        }
    }

    static int find(int x) {
        if (p[x] != x) {
            p[x] = find(p[x]);
        }
        return p[x];
    }

    static int kruskal() {
        Arrays.sort(edges, Comparator.comparingInt(a -> a.w));
        for (int i = 1; i <= n; i++) {
            p[i] = i;
        }
        int res = 0, count = 0;
        for (int i = 0; i < m; i++) {
            int a = edges[i].a, b = edges[i].b, w = edges[i].w;
            a = find(a);
            b = find(b);
            if (a != b) {
                p[a] = b;
                res += w;
                count++;
            }
        }
        //判断是否连通
        return count < n - 1 ? INF : res;

    }

    static int prim() {
        Arrays.fill(dist, INF);
        int res = 0;
        for (int i = 0; i < n; i++) {
            int t = -1;
            for (int j = 1; j <= n; j++) {
                if (!st[j] && (t == -1 || dist[j] < dist[t])) {
                    t = j;
                }
            }
            if (i > 0 && dist[t] == INF) {
                return INF;
            }
            if (i > 0) {
                res += dist[t];
            }
            for (int j = 1; j <= n; j++) {
                dist[j] = Math.min(dist[j], ad[t][j]);
            }
            st[t] = true;

        }
//        System.out.println(Arrays.toString(dist));
        return res;
    }


    public static void main(String[] args) throws Exception {
        map.put(1, "太原");
        map.put(2, "北京");
        map.put(3, "上海");
        map.put(4, "深圳");
        map.put(5, "广州");
        map.put(6, "大同");
        while (isContinue) {
            System.out.println("------------------欢迎来到交通咨询系统-----------------");
            System.out.println("功能列表：");
            System.out.println("1.添加城市及其序号(系统中已经有6个城市)");
            System.out.println("2.列出当前的所有城市");
            System.out.println("3.请选择计算最小生成树的算法（1为Prim算法适用于稠密图；2为Kruskal算法，适用于稀疏图）");
            System.out.println("4.显示两个城市的直接可达距离");
            System.out.println("5.判断是否为连通图");
            System.out.println("6.显示最小生成树的代价");
            System.out.println("7.退出程序");
            System.out.println("请输入序号选择功能(使用功能4，5，6前，必须先用3输入)");
            choose = nextInt();
            switch (choose) {
                case 1:
                    addCity();
                    break;
                case 2:
                    showCity();
                    break;
                case 3:
                    chooseInput();
                    break;
                case 4:
                    showInput();
                    break;
                case 5:
                    isConnected();
                    break;
                case 6:
                    showMinCost();
                    break;
                case 7:
                    isContinue = false;
                    break;
                default:
                    System.out.println("输入错误，请重新输入");
            }
        }

    }
}

